package Year22_Month05.day26;

import java.util.Arrays;

public class 归并排序 {
    public static void main(String[] args) {
        int[] arr = {4,2,8,6,9,1,3,5,0,7};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void mergeSort(int[] arr){
        int[] temp = new int[arr.length];
        mergeSort(arr,0,arr.length,temp);
    }
    public static void mergeSort(int[] arr,int left,int right,int[] temp){
        if(right - left > 1){//如果说当前要排序的元素总数大于1，那么就排，不然就返回
            int mid = left + ((right - left) >> 1);
            //开始进行分组
            mergeSort(arr,left,mid,temp);//先分递归左边的
            mergeSort(arr,mid,right,temp);//再分递归右边的
            mergeSortDate(arr,left,mid,right,temp);//分好了之后就要合并数组了，这个合并是精髓
            System.arraycopy(temp,left,arr,left,right - left);//这里把临时空间已经拍好了序的数组复制到arr数组里面。
        }
    }

    public static void mergeSortDate(int[] arr,int left,int mid,int right,int[] temp){
        //首先定义好指针
        int begin1 = left,end1 = mid;
        int begin2 = mid,end2 = right;
        int index = left;
        //接着开始两个数组的合并
        while(begin1 < end1 && begin2 < end2){
            if(arr[begin1] >= arr[begin2]){
                temp[index++] = arr[begin2++];
            }else{
                temp[index++] = arr[begin1++];
            }
        }
        //最后剩谁就一直往临时空间填就行
        while(begin1 < end1){
            temp[index++] = arr[begin1++];
        }
        while(begin2 < end2){
            temp[index++] = arr[begin2++];
        }
    }
}